using System;
using System.Collections.Generic;
using System.Text;

namespace COME342.CollisionResolution.BinaryTree
{
    public static class util
    {
        /// <summary>
        /// Generates a random string with the given length
        /// </summary>
        /// <param name="size">Size of the string</param>
        /// <param name="lowerCase">If true, generate lowercase string</param>
        /// <returns>Random string</returns>
        public static string RandomString(int size, int seed, bool lowerCase)
        {
            StringBuilder builder = new StringBuilder();
            Random random = new Random(seed);
            char ch;
            for (int i = 0; i < size; i++)
            {
                ch = Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65)));
                builder.Append(ch);
            }
            if (lowerCase)
                return builder.ToString().ToLower();
            return builder.ToString();
        }
    }

    public interface ILischDataRow
    {
        int GetId();
    }

    public interface ILischPseudoLinkRow : ILischDataRow
    {
        int GetPseudoLink();
        void SetPseudoLink(int ps);
    }

    public class SimpleDataRow<T> : ILischDataRow
    {
        int id;
        public T data;

        public int GetId()
        {
            return id;
        }

        public SimpleDataRow(int id, T data)
        {
            this.id = id;
            this.data = data;
        }

        public override string ToString()
        {
            return id.ToString() + ", " + data.ToString();
        }

    }

    public class PseudoLinkRow<T> : ILischPseudoLinkRow
    {
        int id;
        public T data;
        public int pseudolink = -1;

        public int GetId()
        {
            return id;
        }

        public int GetPseudoLink()
        {
            return pseudolink;
        }

        public void SetPseudoLink(int ps)            
        {
            pseudolink = ps;
        }

        public PseudoLinkRow(int id, T data)
        {
            this.id = id;
            this.data = data;
        }

        public PseudoLinkRow(int id, T data, int pseudolink)
        {
            this.id = id;
            this.data = data;
            this.pseudolink = pseudolink;
        }

        public override string ToString()
        {
            return id.ToString() + ", " + data.ToString();
        }

    }

    public class LischTableEntry<T>
    {
        public T data;
        public int link;

        public LischTableEntry(T data, int link)
        {
            this.data = data;
            this.link = link;
        }

        public LischTableEntry(T data)
        {
            this.data = data;
            this.link = -1;
        }

        public override string ToString()
        {
            return data.ToString();
        }
    }

    public class LischTable<T> where T : ILischDataRow
    {
        int size;
        bool isTableFull = false;

        public bool IsTableFull { get { return isTableFull; } }

        List<LischTableEntry<T>> tbl;

        public List<LischTableEntry<T>>.Enumerator GetEnumerator()
        {
            return tbl.GetEnumerator();            
        }


        public LischTableEntry<T> this[int index]
        {
            get { return tbl[index % size]; }
        }

        public LischTable(int size)
        {
            this.size = size;
            tbl = new List<LischTableEntry<T>>(size);

            for (int i = 0; i < size; ++i)
            {
                tbl.Add(default(LischTableEntry<T>));
            }
        }

        // -1 if data does not exist
        public int CountProbes(T data)
        {
            int c = 1;

            if (tbl[data.GetId() % size] == null)
                return -1;

            if (tbl[data.GetId() % size].data.GetId() == data.GetId())
                return 1;

            int index = tbl[data.GetId() % size].link;
            while (tbl[index] != null && tbl[index].data != null)
            {
                c++;
                if (tbl[index].data.GetId() == data.GetId())
                    return c;
                index = tbl[index].link;
            }
            return -1;
        }

        public bool IsColliding(T data)
        {
            return tbl[data.GetId() % size] != null && tbl[data.GetId() % size].data.GetId() != -1;
        }

        public int ApplyBinaryTree(BinaryCollisionResolutionTree<int> btEmpty, T data)
        {
            BinaryCollisionResolutionTree<int> tmp;

            int empty = btEmpty.givenId;

            while (!btEmpty.IsRoot())
            {
                tmp = btEmpty.parent;

                if (tmp.left == btEmpty)
                {                    
                    btEmpty = tmp;                    
                }
                else
                {                    
                    tbl[empty] = tbl[tmp.givenId];
                    btEmpty = tmp;
                    empty = tmp.givenId;
                }
            }

            //tbl[btEmpty.data % size] = new InfinieHashTableEntry<T>(data);
            tbl[empty] = new LischTableEntry<T>(data);
            return -1;
        }

        //returns insertedAt index
        public int InsertAt(int index, T data)
        {
            if (isTableFull)
                return -1;

            if (tbl[index] == null)
            {
                tbl[index] = new LischTableEntry<T>(data);
                return index; // probe = 1
            }

            if (tbl[index].link == -1)
            {
                for (int i = size - 1; i >= 0; --i)
                {
                    if (tbl[i] != null)
                        continue;
                    tbl[i] = new LischTableEntry<T>(data);
                    tbl[index].link = i;
                    return i;
                }
                isTableFull = true;
                return -1;
            }
            else
            {
                return InsertAt(tbl[index].link, data);
            }
        }

        public void DeleteByPosition(int position)
        {
            if (tbl[position].link == -1)
            {
                tbl[position] = null;
                return;
            }

            int indice = tbl[position].link;

            tbl[position].data = tbl[indice].data;
            tbl[position].link = tbl[indice].link;            
            tbl[indice] = null;
        }

        public bool DeleteRecord(T record)
        {
            for (int i = 0; i < size; ++i)
            {
                if (tbl[i] == null || tbl[i].data == null)
                    continue;

                if (tbl[i].data.GetId() == record.GetId())
                {
                    DeleteByPosition(i);
                    return true;
                }
            }
            return false;
        }

    }
}
